package 数据结构和算法.剑指offer.数组.旋转数组的最小数字;

import 工具.打印.PrintUtil;

import java.util.Arrays;

/**
 * 旋转数组的最小数字
 * <p>
 * 第一种方法就是从前向后遍历，直到找到下一个数字比当前小的，那么下一个就是最小值
 * <p>
 * 第一种方法就是使用Java自带的Arrays.sort方法，直接将数组排序，然后返回numbers[0]即可
 */
public class Test {
    public static void main(String[] args) {
        int[] array1 = {3, 4, 5, 0, 2};
        int[] array2 = {5, 6, 7, 0, 2};
        PrintUtil.println(search1(array1));
        PrintUtil.println(search2(array2));
    }

    // 使用二分查找
    public static int search1(int[] array) {
        if (array.length > 0) {
            int left = 0;
            int right = array.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (array[right] < array[mid]) {
                    left = mid + 1;
                } else if (array[right] > array[mid]) {
                    right = mid;
                } else {
                    right--;
                }
            }

            return array[left];
        } else {
            return -1;
        }
    }

    //直接使用Arrays工具
    public static int search2(int[] array) {
        if (array.length > 0) {
            Arrays.sort(array);
            return array[0];
        } else {
            return -1;
        }
    }
}
